有趣的交互题。
题意:有一个递增的单向链表,需要通过询问权值和下一项编号,求出其中 的最小元素。
这还不简单?挨个询问一遍就切了嘛(
,询问最多 次。
笑容逐渐凝固。
考虑其他方法:
因为已知该链表是递增的,可以先随机询问 个点,记录好 的最大元素以及他下一项的地址。因为询问数远小于 的最大可能值,我们将这些询问近似地看做随机的。
经过这些询问后,如果最大元素恰好为 ,直接输出即可,因为不能得到更小的解了。
否则,我们从下一项的地址开始询问最多 次(因为地址随机,两个被询问的数之间数的个数的期望可以通过除法求得,远小于 ),每次移动到获取的 nxt 指针,直到该指针为 或找到 的数。对于第二种,因为单调递增的性质,可以知道获取到的是最优解,直接输出;对于第一种,跳出循环后判断最大值与 的大小关系,输出该值或者 即可。
注意几点:
- 经过几次错误,发现这里翻译得很毒瘤,实际上只能进行 次询问(原文如此,经尝试也确实如此),注意不要被坑。
- C++ 的
rand()好像被毒瘤出题人卡掉了,换了几种方式都在第六个点错了,这里可以利用 int 自然溢出手写一个随机。
甚至这个都被卡了:
srand(time(0));
srand(rand()); srand(rand()+19849);
我是用的随机函数可以见代码。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define per(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define fil(x,y) memset((x), (y), sizeof(x))
using namespace std;
typedef long long ll;
const int N = 5e4+5, inf = 0x3f3f3f3f;
int n, front, x, ans = -inf, nxt;
vector<int> interact(int _) {
printf("? %d\n", _);
fflush(stdout);
int a, b;
scanf("%d%d", &a, &b);
return vector<int>({a, b});
}
void give(int _) {
printf("! %d\n", _);
fflush(stdout);
}
int seed, seed2;
void srand(int x, int y) {seed = x; seed2 = y;}
int frand() {return (seed *= 19260817) += ((seed2 += 114514) ^= 1919810);}
int rand() {int res = frand(); while(res <= 0) res += n; return res;}
int main() {
// srand(time(0));
// srand(rand()); srand(rand()+19849);
srand(998244353, 1000000007);
// rep(i, 1, 100) printf("%d %d %d\n", seed, seed2, rand());
scanf("%d%d%d", &n, &front, &x);
nxt = front;
rep(i, 1, min(n, 1000)-1) {
int pos = rand() % n + 1;
vector<int> res = interact(pos);
if(res[0] <= x && res[0] > ans) nxt = res[1], ans = res[0];
}
if(ans == x) return give(x), 0;
rep(i, 1, 1000) {
if(nxt == -1) break;
vector<int> res = interact(nxt);
if(res[0] >= x) return give(res[0]), 0;
ans = res[0]; nxt = res[1];
}
give(ans>=x?ans:-1);
return 0;
}